package com.zhz.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 350. 两个数组的交集 II
 * 给你两个整数数组nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
 * 应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 * <p>
 * 示例 2:
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 * <p>
 * 提示：
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IntersectionOfTwoArraysII350 {

    public static void main(String[] args) {
        IntersectionOfTwoArraysII350 m = new IntersectionOfTwoArraysII350();
        int[] nums1 = {1, 2, 2, 2, 1};
        int[] nums2 = {2, 2};
        int[] res = m.intersect(nums1, nums2);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 笔记：一开始这边使用了map来存数据的次数，后面看到提示里面有说明数的范围是[1,1000]
     * 因此使用使用一个长度为1001的数组来保存次数
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] s = nums1.length <= nums2.length ? nums1 : nums2;
        int[] b = nums1.length <= nums2.length ? nums2 : nums1;
        int[] tmp = new int[1001];
        ArrayList<Integer> list = new ArrayList<>();
        for (int val : b) {
            tmp[val]++;
        }
        for (int val : s) {
            if (tmp[val] > 0) {
                list.add(val);
                tmp[val]--;
            }
        }
        int[] res = new int[list.size()];
        for (int a = 0; a < list.size(); a++) {
            res[a] = list.get(a);
        }
        return res;
    }

}
